#include "mcode.h"
#include "common.h"
#include "op-list.h"
#include "sym.h"
#include <stdarg.h>

static char buf[4096];
static FILE * output_file;

const char * ss=".data\n_ret: .asciiz \"\\n\"\n.globl main\n\n"\
                ".text\nread:\nli $v0, 5\nsyscall\njr $ra\n\n"\
                "write:\nli $v0, 1\nsyscall\nli $v0, 4\nla $a0, _ret\n"\
                "syscall\nmove $v0, $0\njr $ra\n\n";

static void init(){
    fprintf(output_file,"%s",ss);
}

static void output(const char * fmt,...){
    va_list ap;
    va_start(ap,fmt);
    vfprintf(output_file,fmt,ap);
    va_end(ap);
    fprintf(output_file,"\n");
    return;
}

static void sp_m(int u){
    if(u>=-32768&&u<=32767) output("addi $sp, $sp, %d",u);
    else output("li $t8, %d\nadd $sp, $sp, $t8",u);
}

static void spls(const char * s,int offset,char fmt){
    if(offset>=-32768&&offset<=32767) output("%cw %s, %d($sp)",fmt,s,offset);
    else{
        output("li $t8, %d",offset);
        output("add $t8, $t8, $sp");
        output("%cw %s, 0($t8)",fmt,s);
    }  
}

static const char * register_name[]={
    "$0" ,"$at","$v0","$v1","$a0","$a1","$a2","$a3",
    "$t0","$t1","$t2","$t3","$t4","$t5","$t6","$t7",
    "$s0","$s1","$s2","$s3","$s4","$s5","$s6","$s7",
    "$t8","$t9","$k0","$k1","$gp","$sp","$fp","$ra"
};

static int total_space,total_num,* degree;
static unsigned *recommand;
static int queue[4096],front=0,tail=0;
static int *col;
static active_status * g,left_var,rec2;

static int stack_size,p2;

static void init_graph(int num){
    total_num=num;
    p2=0;
    total_space=(total_num+63)/64*sizeof(uLL);
    int tt2=total_num*sizeof(int);
    degree=malloc(tt2);
    memset(degree,0,tt2);
    front=tail=0;
    g=malloc(total_num*sizeof(active_status));
    for(int i=0;i<total_num;i++){
        g[i]=malloc(total_space);
        memset(g[i],0,total_space);
    }
    stack_size=4;
    col=malloc(tt2);
    memset(col,0,tt2);
    recommand=malloc(tt2);
    memset(recommand,0,tt2);
    rec2=malloc(total_space);
    memset(rec2,0,total_space);
    left_var=malloc(total_space);
    memset(left_var,0,total_space);
    return;
}

#define COL 22

static void free_graph(){
    free(degree);degree=NULL;
    for(int i=0;i<total_num;i++) free(g[i]);
    free(g);g=NULL;
    free(col);col=NULL;
    front=tail=0;
    free(left_var);left_var=NULL;
    free(recommand); recommand=NULL;
    free(rec2); rec2=NULL;
}

static inline int get_pos(const active_status a,const uLL pos){return (a[pos/64]>>(pos%64uLL))&1;}
static inline void merge(active_status x,const active_status y){
    for(int i=0;i<total_space/sizeof(uLL);i++) x[i]|=y[i];
    return;
}
static inline void set_0(active_status x,uLL pos){
    int t=pos/64;pos%=64;
    uLL mask=~(1uLL<<pos);
    x[t]&=mask;
    return;
}

static inline void degree_calc(const uLL pos){
    set_0(g[pos],pos);
    uLL ans=0;
    for(int i=0;i<total_space/sizeof(uLL);i++){
        uLL temp=g[pos][i];
        temp=(temp & 0x5555555555555555uLL)+((temp>> 1uLL) & 0x5555555555555555uLL);
        temp=(temp & 0x3333333333333333uLL)+((temp>> 2uLL) & 0x3333333333333333uLL);
        temp=(temp & 0x0f0f0f0f0f0f0f0fuLL)+((temp>> 4uLL) & 0x0f0f0f0f0f0f0f0fuLL);
        temp=(temp & 0x00ff00ff00ff00ffuLL)+((temp>> 8uLL) & 0x00ff00ff00ff00ffuLL);
        temp=(temp & 0x0000ffff0000ffffuLL)+((temp>>16uLL) & 0x0000ffff0000ffffuLL);
        temp=(temp & 0x00000000ffffffffuLL)+((temp>>32uLL) & 0x00000000ffffffffuLL);
        ans+=temp;
    }
    degree[pos]=ans;
    if(ans<COL) queue[++tail]=pos,left_var[pos/64]|=1uLL<<(uLL)(pos%64uLL);
}

static inline void dec_degree(const int pos){
    for(int i=0;i<total_space/sizeof(uLL);i++){
        uLL x=g[pos][i];
        for(int j=i*64;j<(i+1)*64&&j<total_num;j++,x>>=1) if(x&1){
            --degree[j];
            if(degree[j]<COL&&!get_pos(left_var,j)) queue[++tail]=j,left_var[j/64]|=1uLL<<(uLL)(j%64);
        }
    }
}

static const unsigned reg_ord[]={8,9,10,11,12,13,14,15,3,2,4,5,6,7,16,17,18,19,20,21,22,23};
static const unsigned reg_ord2[]={16,17,18,19,20,21,22,23};

void saver_regs_deal(unsigned int * global_status,char t){
    int curr=4;
    for(unsigned i=16;i<24;i++)if((*global_status>>i)&1){
        spls(register_name[i],-curr,t);
        curr+=4;
    } 
}
static unsigned saved_regs;

static inline void colorVal(unsigned int * global_status){
    for(int i=0;i<total_num;i++) degree_calc(i);
    while(front<tail) dec_degree(queue[++front]);
    for(uLL i=0;i<total_num;i++) 
    if(!((left_var[i/64]>>(i%64uLL))&1)) queue[++tail]=i;
    unsigned int local_status;
    *global_status=0;
    for(int _=tail;_;_--){
        int x=queue[_];
        if(col[x]) continue;
        local_status=0;
        for(int y=0;y<total_num;y++) 
            if(get_pos(g[x],y)&&col[y]>0) local_status|=1u<<col[y];
        if(get_pos(rec2,x)) for(int i=0;i<8;i++) 
            if(!((local_status>>reg_ord2[i])&1)) {
                col[x]=reg_ord2[i];
                break;
            }
        if(!col[x]){
            if(recommand[x]&&!((local_status>>recommand[x])&1)) 
                col[x]=recommand[x];
            else for(int i=0;i<22;i++)
            if(!((local_status>>reg_ord[i])&1)){
                col[x]=reg_ord[i];
                break;
            }   
        }
        if(!col[x]) col[x]=-stack_size-32,stack_size+=4;
        else *global_status|=1u<<col[x];
    }
    saved_regs=0;
    for(unsigned i=16;i<24;i++) 
        saved_regs+=((*global_status>>i)&1)*4;
    stack_size+=saved_regs;

    //for(int i=0;i<total_num;i++) printf("%d:%s\n",i,col[i]>=0?register_name[col[i]]:"OVERFLOW");
    //puts("!!!");
    return;
}

static InterCodes * g_build(InterCodes * now){
    int local_param=0;
    for(now=now->next;now&&now->code.kind!=FUNC;now=now->next) if(now->run){
        InterCode inst=now->code;
        int u=inst.kind;
        Operand x=inst.x;
        if(u!=LABL&&u!=FUNC&&u!=GOTO&&u!=DEC&&u!=PARAM&&u!=ASSADDR&&u!=OP_IF&&u!=RET&&u!=ARG&&u!=WRITE&&u!=READ&&u!=CALL){
            uLL pos=x->offset-1;
            if(!get_pos(now->out,pos)){
                now->run=0;
                continue;
            }
        }
        for(uLL pos=0;pos<total_num;pos++) 
            if(get_pos(now->out,pos)) merge(g[pos],now->out);
        switch(u){
            case DEC:
                stack_size+=inst.info;x->offset=4-stack_size;
                break;
            case ARG:case WRITE:
                if(inst.info<=4&&x->kind==VARIABLE) recommand[x->offset-1]=3+inst.info;
                break;
            case CALL:
            case READ:case RET:
                merge(rec2,now->in);
                if(x->kind==VARIABLE) recommand[x->offset-1]=2;
                break;
            case PARAM:
                ++local_param;
                if(local_param<=4) col[x->offset-1]=3+local_param;
                break;
            default:
                break;
        }   
    }
    return now;
}

static int small_chk(Operand x){return x->kind==CONSTANT&&x->u.value>=-32767&&x->u.value<=32767;}

int val2reg(Operand x,int id){
    if(x->kind==CONSTANT){
        output("li $t%d, %d",8+id,x->u.value);
        return 24+id;
    }
    int c=col[x->offset-1];
    if(c>0) return c;
    if(id!=-1) spls(register_name[24+id],c,'l');
    else id=0;
    return 24+id;
}

void regfixup(Operand x){
    int c=col[x->offset-1];
    if(c<0) spls(register_name[24],c,'s');
    return;
}

static int temp_save=0,param_num=0,status_m;
void caller_regs_deal(active_status x,char c){
    temp_save=0;
    for(int i=0;i<total_num;i++) if(col[i]>0&&col[i]<16&&get_pos(x,i)){
        spls(register_name[col[i]],-stack_size-temp_save,c);
        temp_save+=4;
    }
    return;
}

int cover_target[32];

void move2target(Operand x,int target){
    const char * s=register_name[target];
    if(x->kind==CONSTANT) output("li %s, %d",s,x->u.value);
    else{
        int c=col[x->offset-1];
        if(c<0) spls(s,c,'l');
        else if(c!=target) {
            if(cover_target[c]<0) c=-cover_target[c];
            output("move %s, %s",s,register_name[c]);
        }
    }
    return;
}

void target2v(Operand x,int target){
    const char * s=register_name[target];
    int c=col[x->offset-1];
    if(c<0) spls(s,c,'s');
    else if(c!=target) output("move %s, %s",register_name[c],s);
}

static const char * RELOP_NAME[]={
    "ble","bgt","bge","blt","bne","beq"
};

static inline void coverset(Operand x,int delta){
    if(x->kind==VARIABLE) {
        int c=col[x->offset-1];
        if(c>0&&cover_target[c]>=0) cover_target[c]+=delta;
    }
    return;
}

static void deal_inst(InterCodes * now,unsigned global_status){
    InterCode inst=now->code;
    Operand x=inst.x,y=inst.y,z=inst.z;
    int u=inst.kind,xx,yy,zz;
    const char * xn, * yn, * zn;
    switch(u){
        case LABL:
            if(x->offset) output("L%u:",x->u.label);
            return;
        case ASSIGN: 
            xx=val2reg(x,-1);xn=register_name[xx];
            if(y->kind==CONSTANT) output("li %s, %d",xn,y->u.value);
            else {
                yy=val2reg(y,0);yn=register_name[yy];
                if(xx!=yy) output("move %s, %s",xn,yn);   
            }
            regfixup(x);
            return;
        case ADD:
            xx=val2reg(x,-1);xn=register_name[xx];
            if(y->kind==CONSTANT&&z->kind==CONSTANT) output("li %s, %d",xn,y->u.value+z->u.value);
            else if(small_chk(y)){
                zz=val2reg(z,1);zn=register_name[zz];
                output("addi %s, %s, %d",xn,zn,y->u.value);
            }else if(small_chk(z)){
                yy=val2reg(y,0);yn=register_name[yy];
                output("addi %s, %s, %d",xn,yn,z->u.value);
            }else{
                yy=val2reg(y,0);yn=register_name[yy];
                zz=val2reg(z,1);zn=register_name[zz];
                output("add %s, %s, %s",xn,yn,zn);
            }
            regfixup(x);
            return;
        case SUB:
            xx=val2reg(x,-1);xn=register_name[xx];
            if(y->kind==CONSTANT&&z->kind==CONSTANT) output("li %s, %d",xn,y->u.value-z->u.value);
            else if(small_chk(y)){
                zz=val2reg(z,1);zn=register_name[zz];
                output("sub %s, $0, %s",xn,zn);
                if(y->u.value) 
                    output("addi %s, %s, %d",xn,xn,y->u.value);
            }else if(small_chk(z)){
                yy=val2reg(y,0);yn=register_name[yy];
                output("addi %s, %s, %d",xn,yn,-z->u.value);
            }else{
                yy=val2reg(y,0);yn=register_name[yy];
                zz=val2reg(z,1);zn=register_name[zz];
                output("sub %s, %s, %s",xn,yn,zn);
            }
            regfixup(x);
            return;
        case MUL:
            xx=val2reg(x,-1);xn=register_name[xx];
            yy=val2reg(y,0);yn=register_name[yy];
            zz=val2reg(z,1);zn=register_name[zz];
            output("mul %s, %s, %s",xn,yn,zn);
            regfixup(x);
            return;
        case OP_DIV:
            xx=val2reg(x,-1);xn=register_name[xx];        
            yy=val2reg(y,0);yn=register_name[yy];
            zz=val2reg(z,1);zn=register_name[zz];
            output("div %s, %s",yn,zn);
            output("mflo %s",xn);
            regfixup(x);
            return;
        case GTADDR:
            xx=val2reg(x,-1);xn=register_name[xx];
            if(y->offset>=-32768&&y->offset<32767)
                output("addi %s, $sp, %d",xn,y->offset-saved_regs);
            else output("li %s, %d\nadd %s, $sp, %s",xn,y->offset-saved_regs,xn,xn);
            regfixup(x);
            return;
        case TOADDR:
            xx=val2reg(x,-1);xn=register_name[xx];
            yy=val2reg(y,0);yn=register_name[yy];
            output("lw %s, 0(%s)",xn,yn);
            regfixup(x);
            return;
        case ASSADDR:
            xx=val2reg(x,1);xn=register_name[xx];
            yy=val2reg(y,0);yn=register_name[yy];
            output("sw %s, 0(%s)",yn,xn);
            return;
        case GOTO:
            output("j L%u",x->u.label);
            return;
        case OP_IF:
            xx=val2reg(x,1);xn=register_name[xx];
            yy=val2reg(y,0);yn=register_name[yy];
            output("%s %s, %s, L%u",RELOP_NAME[inst.info],xn,yn,z->u.label);
            return;
        case RET:
            move2target(x,2);
            saver_regs_deal(&global_status,'l');
            output("lw $ra, 0($sp)");
            output("jr $ra");
            return;
        case ARG:case WRITE:
            if(!status_m){
                status_m=1;
                param_num=0;
                InterCodes * tp=now;
                while(tp->code.info!=1) coverset(tp->code.x,1),tp=tp->next;
                coverset(tp->code.x,1);
                caller_regs_deal(tp->out,'s');
            }
            if(inst.info>4) {
                xx=val2reg(x,1);xn=register_name[xx];
                spls(xn,-stack_size-temp_save-param_num,'s'),param_num+=4;
            }else {
                int tt=3+inst.info;
                if(cover_target[tt]>0&&!(x->kind==VARIABLE&&tt==col[x->offset-1])){
                    int md=8;while(cover_target[md]!=0) md++;
                    output("move %s, %s",register_name[md],register_name[tt]);
                    cover_target[tt]=-md;
                    cover_target[md]=1;
                }    
                move2target(x,3+inst.info);
            }
            coverset(x,-1);
            if(u!=WRITE) return;
        case CALL:case READ:
            if(!status_m){
                status_m=1;
                param_num=0;
                caller_regs_deal(now->in,'s');
            }
            xx=val2reg(x,-1);xn=register_name[xx];
            int size=stack_size+temp_save+param_num;
            sp_m(-size);
            if(u==READ) output("jal read");
            else if(u==WRITE) output("jal write");
            else if(strcmp(y->u.name,"main")==0) output("jal %s",y->u.name);
            else output("jal f_%s",y->u.name);
            sp_m(size);
            if(u!=WRITE&&get_pos(now->out,x->offset-1)) target2v(x,2);
            caller_regs_deal(u==WRITE?now->out:now->in,'l');
            temp_save=0;param_num=0;status_m=0;
            memset(cover_target,0,sizeof(cover_target));
            return;
        case PARAM:
            p2++;
            if(p2>4){
                int pos=col[x->offset-1];
                if(pos>0) spls(register_name[pos],(p2-4)*4,'l');
                else{
                    spls("$t8",(p2-4)*4,'l');
                    spls("$t8",pos,'s');
                }
            }
            return;
        default: return;
    }
    return;
}

InterCodes * deal_func(InterCodes * first_op){
    Assert(first_op->code.kind==FUNC,"not a function start!");
    if(!first_op->run){
        first_op=first_op->next;
        while(first_op&&!first_op->run) first_op=first_op->next;
        return first_op;
    }
    const char * name=first_op->code.x->u.name;
    init_graph(first_op->code.x->offset);
    if(strcmp(name,"main")==0) output("%s:",name);
    else output("f_%s:",name);
    InterCodes * endcode=g_build(first_op);
    unsigned global_status=0;
    colorVal(&global_status);
    output("sw $ra, 0($sp)");
    saver_regs_deal(&global_status,'s');
    for(first_op=first_op->next;first_op;first_op=first_op->next){
        if(first_op->code.kind==FUNC) break;
        if(first_op->run) deal_inst(first_op,global_status);
    }
    output("\n");
    free_graph();
    return endcode;
}

void interperter(FILE * out,InterCodes * first_op){
    output_file=out;
    init();
    for(InterCodes * now=first_op;now;now=deal_func(now));
    fclose(out);
}
